/*
Implement pow(x, n).
*/

class Solution {
public:
    /*
     x^n = 1 (n = 0)
           x^(n/2) * x^(n/2) (n is even)
           x^((n-1)/2) * x^((n-1)/2) * x (n is odd and n > 0)
           x^((n+1)/2) * x^((n+1)/2) * 1.0/x (n is odd and n < 0)
    */
    double pow(double x, int n) {
        if (!n) return 1;
        if (x == 0.0) return x;
        double res;
        double half = pow(x, n/2);
        if (n % 2 == 0) {
            res =  half * half;
        } else if ((n % 2) && n > 0) {
            res = half * half * x;
        } else {
            res = half * half / x;
        }
        return res;
    }
};
#if 0
class Solution {
public:
    double pow(double x, int n) {
        if (!n) return 1.0;
        if (!x) return 0.0;
        int negative = 0;
        double res = x;
        double extra = 1.0;
        if (n < 0) {
            n = -n;
            if (n == -n) {
                /* special case where
                   x = -2147483648 */
                extra *= x;
                n = -(n + 1);
            }
            negative = 1;
        }
        while (n > 1) {
            if (n % 2) {
                extra *= res;
            }
            res *= res;
            n /= 2;
        }
        res *= extra;
        if (negative) {
            res = 1.0 / res;
        }
        return res;
    }
};
#endif
